package com.miracle;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 *
 *
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
 *提示：
 *
 * 链表中节点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 109
 *
 * @author : miracle
 * @version : 1.0.0
 * @date : 2021/3/27 9:55
 */
public class RotateRight {


    public static void main(String[] args) {

        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode listNode = rotateRight1(head, 2);
        while (listNode != null) {
            System.out.println(listNode.val);

            listNode = listNode.next;
        }

    }

    /**
     *  超过时间限制
     * @param head
     * @param k
     * @return
     */
    public static ListNode rotateRight(ListNode head, int k) {

        if (head == null) {
            return null;
        }
        List<Integer> all = new ArrayList<>();
        while (head != null) {
            /**/
            all.add(head.val);
            head = head.next;
        }
        all.sort(Comparator.reverseOrder());
        for (int i = 0; i < k; i++) {
            all.add(all.remove(0));
        }
        ListNode result = new ListNode(0);
        for (Integer integer : all) {
            ListNode listNode = new ListNode(integer);
            listNode.next = result.next;
            result.next = listNode;
        }

        return result.next;

    }

    public static ListNode rotateRight1(ListNode head, int k) {

        if (head == null) {
            return null;
        }

        ListNode temp = head;
        int n = 1;

        /* 记录链表长度*/
        while (temp.next != null) {
            temp = temp.next;
            n++;
        }
        /* 判断需要移动到第几个 */
        int i = n - k % n;
        /* 如果正好移动了链表长度=不移动*/
        if (i == n) {
            return head;
        }
        /* 形成闭合链表 */
        temp.next = head;
        /* 移动到需要移动的位置*/
        while (i-- > 0) {
            temp = temp.next;
        }
        ListNode ret = temp.next;
        /* 解除闭合 */
        temp.next = null;
        return ret;

    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
